package com.shr.code_interview;

public class Solution_11 {
    public static int minNumberInRotateArray(int [] array) {
    	int front = 0 ;
    	int end = array.length - 1;
    	int mid = front;
        while(array[front] >= array[end]){
        	if(end - 1 == front){
        		mid  = end;
        		break;
        	}
        	mid = (front + end) / 2;
        	
        	if (array[mid] == array[front] && array[mid] == array[end])
        		return linearSearch(array) ;
        	
        	if(array[mid] <= array[end])
        		end = mid ;
        	else if(array[mid] >= array[front])
        		front = mid ;
        }
        return array[mid];
    }
	private static int linearSearch(int[] array) {
		int minVal = Integer.MAX_VALUE ; 
		for(int i = 0;i < array.length;i++){
			minVal = Math.min(array[i], minVal) ;
		}
		return minVal ;
	}
	public static void main(String[] args) {
		int[] array = {2,3,4,5,0,1};
		System.out.println(minNumberInRotateArray(array));
	}
}
